package com.leetcode;

import java.util.ArrayList;

import org.testng.annotations.Test;

public class Triangle {
	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int N = triangle.size();
		if (N == 0) return 0;
		
		int[] a = new int[N+1];
		for (int level = N-1; level>=0; level--) {
			ArrayList<Integer> list = triangle.get(level);
			for (int i=0; i<=level; i++) {
				a[i] = list.get(i) + Math.min(a[i], a[i+1]);
			}
		}
		
		return a[0];
    }
	
	@Test
	public void test1() {
		ArrayList a = new ArrayList();
		ArrayList<Integer> b1 = new ArrayList<Integer>();
		b1.add(1);
		ArrayList<Integer> b2 = new ArrayList<Integer>();
		b2.add(2);
		b2.add(3);
		a.add(b1);
		a.add(b2);
		int res = new Triangle().minimumTotal(a);
		System.out.println();
	}
}
